package com.algorithm.graph.test;

import java.io.*;
import java.util.*;

/**
 * 有向图  https://blog.csdn.net/Admzy/article/details/121842596
 *
 * 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
 * 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
 *
 * 数据范围
 * 1 ≤ n ≤ 500
 * 1 ≤ m ≤ 10^5
 * 图中涉及边长均不超过10000。
 */
class Dijkstra2 {
    private static int N = 510;
    private static int[][] g = new int[N][N];  //为稠密阵所以用邻接矩阵存储
    private static boolean[] st = new boolean[N];  //用于记录该点的最短距离是否已经确定
    private static int[] dist = new int[N];  //用于记录每一个点距离第一个点的距离
    private static int n;
    private static int max = 5000000; 

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = bufferedReader.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        int m = 0;
        m = Integer.parseInt(str1[1]);

        // n*m
        n = 12;

        for (int i = 1; i <= n; i ++) {
            Arrays.fill(g[i], max); //初始化图 因为是求最短路径 所以每个点初始为无限大
        }
        for (int i = 0; i < m; i ++) {
            String[] str2 = bufferedReader.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            int c = Integer.parseInt(str2[2]);
            g[a][b] = Math.min(g[a][b], c);  //如果发生重边的情况则保留最短的一条边
        }

        System.out.println(dijkstra());
        bufferedReader.close();
    }

    public static int dijkstra() {
        Arrays.fill(dist, max);  //初始化距离  0x3f代表无限大
        dist[1] = 0;  //第一个点到自身的距离为0

        for (int i = 0; i < n; i ++) {
            int t = -1; //t存储当前访问的点
            for (int j = 1; j <= n; j ++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }
            st[t] = true;
            for (int j = 1; j <= n; j ++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]); //依次更新每个点所到相邻的点路径值
            }
        }
        if (dist[n] == max) {
            return -1;
        } else {
            return dist[n];
        }
    }
}

